package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author waxijiang
 * 二叉树的先序遍历
 */
public class PreOrderTraversal {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = null;
        node.right = new TreeNode(2);
        node.right.left = new TreeNode(3);
        node.right.right = null;

        System.out.println(preorderTraversal(node));

    }

    public static List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        // 排除特殊
        if (root != null) {
            stack.add(root);
        }

        List<Integer> result = new ArrayList<>();
        while (!stack.empty()) {
            TreeNode tmpNode = stack.pop();
            result.add(tmpNode.val);
            if (tmpNode.right != null) {
                stack.add(tmpNode.right);
            }
            if (tmpNode.left != null) {
                stack.add(tmpNode.left);
            }
        }
        return result;
    }

}


